Radio frequency identification (RFID) is one of core technologies of a ubiquitous computing generation. RFID systems are a non-contact system for identifying many objects in wide range through wireless communication between readers and tags. Particularly, the RFID system has been receiving attention as alternative of barcodes which have been widely used in physical distribution and financial service because the RFID system does not require direct contact and scanning unlike barcodes.
When a reader requests tags in an identifiable area to transmit identification numbers thereof in order to read information stored in tags in the RFID system, the tags transmit own identification number to the reader as a response for the request. However, when a plurality of tags transmit identification number to a reader at the same time, tag collision occurs. That is, when a tag transmits its information to a reader, tag collision occurs if other tags transmit their information to the same reader at the same time.
Tag collision causes a reader not to identify tags correctly and rapidly, thereby deteriorating the efficiency of a system. However, passive tags do not have abilities to solve it for themselves, because of a limited function and low cost. Thus, how to solve the program efficiently is one of the most important issues in RFID system.
Tag anti-collision protocols were separated into ALOHA based protocols and tree-based protocols.
One of the best known and the most popular tag anti-collision protocols is Framed-Slotted ALOHA (FSA).
As shown in FIG. 1a, basic framed slotted ALOHA (BFSA) identifies tags using a fixed frame size. When a reader provides necessary information such as a frame size and a random number to tags, tags receive the provided information and transmit ID numbers thereof at a calculated time slot in a frame. Here, if tag-collision occurs in one time slot, collided tags retransmit ID numbers at a next reading frame. Because of the fixed frame size of BFSA, implementation is rather easy. If, however, there are too many tags, most of timeslots experience collisions, and none of tags may be identified during long time. And many timeslots may be wasted by idle slots if the number of timeslots in the frame is much larger than that of tags.
A dynamic framed-slotted ALOHA (DFSA) algorithm can actively deal with the problem of BFSA by estimating the number of tags before tag identification and changing the frame size for efficient tag identification. The simplest DFSA algorithm changes the frame size based on the number of timeslots collided. That is, if the number of timeslots collided is larger than a threshold, a reader increases the frame size at the next frame. On the contrary, if the number of collisions is smaller than a threshold, a reader decreases the frame size at the next frame. The DFSA algorithm provides the optimal performance when the frame size is equal to the number of tags. However, the DFSA algorithm cannot accurately estimate the number of tags because the probability of collision increases when the number of tags is larger than an initial frame size.
In a tree based RFID protocol, binary tree algorithms are mostly used. FIG. 1b illustrates a binary tree algorithm. In the binary tree algorithm, if a collision occurs at one time slot, collided tags are randomly separated into two subgroups until all the tags are successfully identified by a reader. The binary tree algorithm is very efficient when the number of tags is small. When the number of tags is large, many collisions occur at the early state. Therefore, many time slots are wasted.
As a compromise of DFSA and binary tree algorithm, a framed-slotted ALOHA with tag estimation and binary splitting (EBFSA) was introduced in an article entitled “Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection” IEEE Communication Letters, vol. 11, no. 5, pp. 452-454, 2007. FIG. 1c illustrates an EBFSA algorithm according to the related art. As shown, EBFSA algorithm is divided into estimation phase and identification phase. A reader performs tag estimation using a fixed frame size Lest in the estimation phase. Since it is difficult to accurately estimate the number of tags if a collision probability exceeds a threshold, a reader decreases the number of tags using a bit mask. This process is repeated until the probability of collision is lower than a threshold. After the estimation phase, the identification phase starts. The initial frame size of identification phase is determined by the tag estimation. In the identification phase, when the tags are collided in a timeslot, a reader resolves the collision by binary tree algorithm. The EBFSA algorithm may improve performance by taking the advantages of the DFSA algorithm and a tree based protocol. However, the EBFSA still needs additional time slots to estimate the number of tags.